{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3563a624",
   "metadata": {},
   "source": [
    "# 机器读心术之文本挖掘与自然语言处理第7课书面作业\n",
    "学号：207402  \n",
    "\n",
    "**作业内容：**  \n",
    "1. 针对李航书第例11.3  \n",
    "1）为什么在例子里我们还没有给出具体的观测序列x，就已经能推算最佳标注序列y*？  \n",
    "2）例子里面已经用手算实现了维特比算法，请用任何一种您熟悉的编程语言将其写为程序，并将例题中的数据条件或特征函数稍微改写，验证你的程序工作正常，需要抓图验证过程  \n",
    "2. 了解布隆过滤器原理（比如可以参考http://www.cnblogs.com/haippy/archive/2012/07/13/2590351.html）\n",
    "假设汉语自动分词基于一拥有20万词汇的词典，合理构造一布隆过滤器（也可结合其它数据结构或算法），用于检查待检测词在词典中是否存在，要求布隆过滤器本身的误算率（False Positive）不超过1/100，需要说明推算的依据。本题只需要文字说明即可，不一定需要（伪）代码"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e0f202b",
   "metadata": {},
   "source": [
    "## 1. 作业1\n",
    "1. 针对李航书第例11.3  \n",
    "1）为什么在例子里我们还没有给出具体的观测序列$x$，就已经能推算最佳标注序列$y^*$？  \n",
    "2）例子里面已经用手算实现了维特比算法，请用任何一种您熟悉的编程语言将其写为程序，并将例题中的数据条件或特征函数稍微改写，验证你的程序工作正常，需要抓图验证过程"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ebd18de3",
   "metadata": {},
   "source": [
    "李航书例11.3如下：  \n",
    "**例11.3** 在例11.1中，用维特比算法求给定的输入序列（观测序列）$x$对应的最优输出序列（标记序列）$y^*=(y_1^*,y_2^*,y_3^*)$。  \n",
    "\n",
    "例11.1如下：  \n",
    "**例11.1** 设有一标注问题：输入观测序列为$X=(X_1,X_2,X_3)$，输出标记序列为$Y=(Y_1,Y_2,Y_3)$，$Y_1,Y_2,Y_3$取值于{1,2}。\n",
    "假设特征$t_k,s_l$和对应的权值$\\lambda_k,\\mu_l$如下："
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0a43771",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "t_1&=t_1(y_{i-1}=1,y_i=2,x,i), \\quad i=2,3\\;,&\\lambda_1=1 \\\\\n",
    "t_2&=t_2(y_{1}=1,y_2=1,x,2),&\\lambda_2=0.5 \\\\\n",
    "t_3&=t_3(y_{2}=2,y_3=1,x,3),&\\lambda_3=1 \\\\\n",
    "t_4&=t_4(y_{1}=2,y_2=1,x,2),&\\lambda_4=1 \\\\\n",
    "t_5&=t_5(y_{2}=2,y_3=2,x,3),&\\lambda_5=0.2 \\\\\n",
    "s_1&=s_1(y_1=1,x,1),&\\mu_1=1 \\\\\n",
    "s_2&=s_2(y_i=2,x,i), \\quad i=1,2\\;,&\\mu_2=0.5 \\\\\n",
    "s_3&=s_3(y_i=1,x,i), \\quad i=2,3\\;,&\\mu_3=0.8 \\\\\n",
    "s_4&=s_4(y_3=2,x,3),&\\mu_4=0.5 \\\\\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75e2e819",
   "metadata": {},
   "source": [
    "对给定的观测序列x,求标记序列为$y=\\{y_1,y_2,y_3\\}=\\{1,2,2\\}$的非规范化条件概率。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4549728b",
   "metadata": {},
   "source": [
    "**解题：**  \n",
    "1）我们可以看出所有的特征$t_k,s_l$都与观测序列$x$没有关系，因此基于条件概率场维特比算法来推最佳标记$y^*$时不需要知道$x$。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3aeb7b59",
   "metadata": {},
   "source": [
    "2）下面用python实现维特比算法来计算例11.1:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "id": "69efe684",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "delta:\n",
      "[[1.  0.5]\n",
      " [2.3 2.5]\n",
      " [4.3 3.8]]\n",
      "y*: [1, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "def viterbi_proc(F,w,x,m):\n",
    "    '''\n",
    "    输入：\n",
    "    F:特征向量\n",
    "    w:权值向量\n",
    "    x:观测序列\n",
    "    输出：\n",
    "    最优路径y*=[y1*,y2*,...,yn*]\n",
    "    '''\n",
    "    n=len(x)\n",
    "    delta=np.zeros((n,m))\n",
    "    i=1\n",
    "    for j in range(m):\n",
    "        delta[i-1][j]=np.dot(w,get_F(0,j+1,x,i,F))\n",
    "    i+=1\n",
    "    phi=np.zeros((n,m))#记录内容从1开始编址\n",
    "    while i <= n:\n",
    "        for l in range(m):\n",
    "            t=np.zeros(m)\n",
    "            for j in range(m):\n",
    "                t[j]=np.dot(w,get_F(j+1,l+1,x,i,F))+delta[i-2][j]\n",
    "#             print('t:',t)\n",
    "            delta[i-1][l]=np.max(t)\n",
    "            phi[i-1][l]=np.argmax(t)+1\n",
    "        i+=1\n",
    "    print('delta:')\n",
    "    print(delta)\n",
    "    y_max = np.argmax(delta[n-1])+1\n",
    "    output=[]\n",
    "    output.append(y_max)\n",
    "    for t in range(n-1):\n",
    "        # print(y_max)\n",
    "        y_max = int(phi[n-1-t][int(y_max)-1])\n",
    "        output.append(y_max)\n",
    "    output.reverse()\n",
    "    return output\n",
    "\n",
    "# 下面定义特征函数t_k和s_l\n",
    "def t1(y_i_1,y_i,x,i):\n",
    "    if y_i_1==1 and y_i==2 and (i ==2 or i==3):\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "\n",
    "def t2(y_i_1,y_i,x,i):\n",
    "    if y_i_1==1 and y_i==1 and (i == 2):\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "\n",
    "def t3(y_i_1,y_i,x,i):\n",
    "    if y_i_1==2 and y_i==1 and (i == 3):\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "    \n",
    "def t4(y_i_1,y_i,x,i):\n",
    "    if y_i_1==2 and y_i==1 and (i == 2 ):\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "    \n",
    "def t5(y_i_1,y_i,x,i):\n",
    "    if y_i_1==2 and y_i==2 and (i == 3):\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "\n",
    "def s1(y_i_1,y_i,x,i):\n",
    "    if y_i==1 and (i == 1):\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "    \n",
    "def s2(y_i_1,y_i,x,i):\n",
    "    if y_i==2 and (i == 1 or i == 2):\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "    \n",
    "def s3(y_i_1,y_i,x,i):\n",
    "    if y_i==1 and (i == 2 or i==3):\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "    \n",
    "def s4(y_i_1,y_i,x,i):\n",
    "    if y_i==2 and (i == 3):\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "\n",
    "#获得特征t_k和s_l的具体数值\n",
    "def get_F(y_i_1,y_i,x,i,F):\n",
    "    f=np.zeros(len(F))\n",
    "    for j in range(len(F)):\n",
    "        f[j]=F[j](y_i_1,y_i,x,i)\n",
    "    return f\n",
    "\n",
    "w=np.array([1.,0.5,1.,1.,0.2,1.,0.5,0.8,0.5]) #权值向量\n",
    "F=[t1,t2,t3,t4,t5,s1,s2,s3,s4] #特征函数，这里存储的是特征函数，计算每一步通过调用get_F函数得到每一步的特征向量\n",
    "\n",
    "y_star=viterbi_proc(F,w,[1,1,1],2)\n",
    "print('y*:',y_star)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "610e308c",
   "metadata": {},
   "source": [
    "可以看出这里计算的结果虽然与李航书一致，但是计算过程中有出入的：\n",
    "1. 本作业中：$\\delta_1(1)=1, \\delta_1(2)=0.5$，与李航书一致；  \n",
    "2. 本作业中：$\\delta_2(1)=2.3, \\delta_2(2)=2.5$，李航书：$\\delta_2(1)=1.6, \\delta_2(2)=2.5$，两者不一致；  \n",
    "3. 本作业中：$\\delta_3(1)=4.3, \\delta_3(2)=3.8$，李航书：$\\delta_3(1)=4.3, \\delta_3(2)=3.2$，两者不一致；  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "823701d4",
   "metadata": {},
   "source": [
    "查阅了李航《统计学习方法》一书的勘误表：  \n",
    "http://www.hangli-hl.com/uploads/3/4/4/6/34465961/errata.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "224778cd",
   "metadata": {},
   "source": [
    "有如下修正(第208页)："
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b01331ab",
   "metadata": {},
   "source": [
    "![err](https://gitee.com/dotzhen/cloud-notes/raw/master/err.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ce00e32",
   "metadata": {},
   "source": [
    "上面的勘误表中给出的还是有问题:\n",
    "1. $\\delta_2(1)=max\\{1+\\lambda_2t_2+\\mu_3s_3,0.5+\\lambda_4t_4+\\mu_3s_3\\}$，这一步没错。再往下计算，$\\delta_2(1)=max\\{1+\\lambda_2t_2+\\mu_3s_3,0.5+\\lambda_4t_4+\\mu_3s_3\\}=max\\{1+0.5+0.8,0.5+1+0.8\\}=max\\{ 2.3, 2.3\\} = 2.3$,哪来的2.4?  \n",
    "2. 因为$\\delta_2(1)$有错误，导致$\\delta_3(1),\\delta_3(2)$都有问题。但是不影响整体结果。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81a1d90e",
   "metadata": {},
   "source": [
    "## 2. 作业2\n",
    "了解布隆过滤器原理（比如可以参考http://www.cnblogs.com/haippy/archive/2012/07/13/2590351.html） 假设汉语自动分词基于一拥有20万词汇的词典，合理构造一布隆过滤器（也可结合其它数据结构或算法），用于检查待检测词在词典中是否存在，要求布隆过滤器本身的误算率（False Positive）不超过1/100，需要说明推算的依据。本题只需要文字说明即可，不一定需要（伪）代码。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cec6e170",
   "metadata": {},
   "source": [
    "**解题：**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ebe6060d",
   "metadata": {},
   "source": [
    "**2.1 布隆过滤器原理**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3bb2f3e8",
   "metadata": {},
   "source": [
    "（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率（假正例False positives，即Bloom Filter报告某一元素存在于某集合中，但是实际上该元素并不在集合中）和删除困难，但是没有识别错误的情形（即假反例False negatives，如果某个元素确实没有在该集合中，那么Bloom Filter 是不会报告该元素存在于集合中的，所以不会漏报）。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1f3a254a",
   "metadata": {},
   "source": [
    "![bulong](https://gitee.com/dotzhen/cloud-notes/raw/master/bulong-1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "950caeda",
   "metadata": {},
   "source": [
    "如上图所示。词典中只有“北京”一词，没有“天安门”和“深圳”两个词。\n",
    "* “北京”经过散列后，查表为1，表示存在；\n",
    "* \"天安门\"经过散列后，查表为0，表示不存在。此时是确定性的不存在，不然散列值找到的元素不会为0； \n",
    "* \"深圳\"经过散列后，查表为1，表示存在，这个结果误查了。误算的原因就在这里，散列函数计算的结果有可能出现重叠。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8902a673",
   "metadata": {},
   "source": [
    "**2.2 达成误算率<=0.01的思路**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e1bf1ae",
   "metadata": {},
   "source": [
    "要想使误算率<=0.01，那么思路上我认为有两种：\n",
    "1. **牺牲空间降误算率**：通过加大哈希表空间来降低误算率，我们可以假设散列是可以理想将结果分散到整个空间，那么只要哈希表空间足够大，可以将误算率下降到指定要求。**但这种方式会增加存储空间的成本。**  \n",
    "2. **牺牲时间降误算率**：通过多次哈希操作来降低误算率，我们可以选择多个不同的散列函数，一次查找，如果多次散列结果都为1才表示存在，两个不同词语通过多次散列算出的结果一样的概率会大大下降，从而使误算率下降。**但这种方式会增加查找时间消耗。**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4069360d",
   "metadata": {},
   "source": [
    "下面我们算一下**误算率**的情况："
   ]
  },
  {
   "cell_type": "markdown",
   "id": "722b2ebf",
   "metadata": {},
   "source": [
    "我们假设哈希表空间为$m$，使用了$k$个散列函数，误算率为$p$。则在哈希表数组中某一特定的位在进行元素插入时经过1次散列没有被置1的概率是：  \n",
    "$$\n",
    "1-\\frac{1}{m}\n",
    "$$\n",
    "那么在所有k次散列操作后该位都没有被置1的概率是：\n",
    "$$\n",
    "(1-\\frac{1}{m})^k\n",
    "$$\n",
    "如果我们插入了n个元素，那么某一位仍然未被置1的概率是：\n",
    "$$\n",
    "(1-\\frac{1}{m})^{kn}\n",
    "$$\n",
    "假设已经完成n个元素的插入，此时查找某个单词，经过1次散列后定位到一个哈希表项，该表项为1的概率为：\n",
    "$$\n",
    "1-(1-\\frac{1}{m})^{kn}\n",
    "$$\n",
    "然后，如果是经过k次不同散列函数，并且表项都为1的概率为(这种情况有可能会被判为误算)：\n",
    "$$\n",
    "(1-(1-\\frac{1}{m})^{kn})^k\\approx(1-e^{-\\frac{kn}{m}})^k\n",
    "$$\n",
    "即,**误算率公式**为：\n",
    "$$\n",
    "p=(1-e^{-\\frac{kn}{m}})^k \\tag{1}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06f667f3",
   "metadata": {},
   "source": [
    "**上述误算率公式可以看出：在记录元素（即n）确定的情况下，哈希表空间（即m)越大，则误算率越低；同时增加散列操作（即加大k)也会使误算率越低。这个与前面根据直观理解得到的“牺牲空间降误算率”和“牺牲时间降误算率”是一致的。**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8be84e8",
   "metadata": {},
   "source": [
    "我们可以再往下推导，假设$n$与$m$已经确定，此时$p=p(k)$，我们求$k$要使误算率p达到最小值，即求$p'(k)=0$的$k$值："
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e2d5417",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "p(k)&=(1-e^{-\\frac{kn}{m}})^k \\\\\n",
    "\\ln{p(k)}&=k\\ln{(1-e^{-\\frac{kn}{m}})} \\\\\n",
    "[\\ln{p(k)}]'&=[k\\ln{(1-e^{-\\frac{kn}{m}})}]' \\\\\n",
    "\\frac{p'}{p} &= \\ln{(1-e^{-\\frac{kn}{m}})}+\\frac{\\frac{kn}{m}e^{-\\frac{kn}{m}}}{1-e^{-\\frac{kn}{m}}} \\\\\n",
    "p'&=(1-e^{-\\frac{kn}{m}})^k[\\ln{(1-e^{-\\frac{kn}{m}})}+\\frac{\\frac{kn}{m}e^{-\\frac{kn}{m}}}{1-e^{-\\frac{kn}{m}}}] \\tag{2}\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1ebdac18",
   "metadata": {},
   "source": [
    "我们记$x=e^{-\\frac{kn}{m}}$，则式(2)可以改写为："
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e31b144d",
   "metadata": {},
   "source": [
    "$$\n",
    "p'=(1-x)^k[\\ln{(1-x)}-\\frac{x\\ln{x}}{1-x}] \\tag{3}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2b7edde",
   "metadata": {},
   "source": [
    "要满足$p'=0$，即：\n",
    "$$\n",
    "\\begin{align*}\n",
    "(1-x)^k[\\ln{(1-x)}-\\frac{x\\ln{x}}{1-x}]=0\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d57eaca",
   "metadata": {},
   "source": [
    "要么，\n",
    "$$\n",
    "\\begin{align*}\n",
    "1-x&=0 \\\\\n",
    "x&=1 \\\\\n",
    "e^{-\\frac{kn}{m}}&=1\\\\\n",
    "k&=0\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "925220f5",
   "metadata": {},
   "source": [
    "要么，\n",
    "$$\n",
    "\\begin{align*}\n",
    "\\ln{(1-x)}-\\frac{x\\ln{x}}{1-x}&=0 \\\\\n",
    "(1-x)\\ln{(1-x)}&=x\\ln{x} \\\\\n",
    "1-x&=x \\\\\n",
    "x&=\\frac{1}{2} \\\\\n",
    "e^{-\\frac{kn}{m}}&=\\frac{1}{2} \\\\\n",
    "k&=\\frac{m}{n}\\ln2 \\tag{4}\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c0f8601b",
   "metadata": {},
   "source": [
    "显然k=0不符合我们的预期，于是在假设m与n确定时，$k=\\frac{m}{n}\\ln2$时误算率p达到最小，将(4)式代入(1)式即可得此时p值："
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9d4b863",
   "metadata": {},
   "source": [
    "$$\n",
    "p=(1-e^{-\\ln2})^{\\frac{m}{n}\\ln2}=((\\frac{1}{2})^{\\ln2})^{\\frac{m}{n}}\\approx 0.6185^{\\frac{m}{n}} \\tag{5}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e8ba82d",
   "metadata": {},
   "source": [
    "本题中要求$p \\le \\frac{1}{100}$，同时记录元素(20万词汇的词典)要求$n=200000$，用公式(5)可计算得$m\\approx 1916992$，再用公式(4)可计算得$k\\approx 7$。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10764bc9",
   "metadata": {},
   "source": [
    "因此，我们的方法是构造一个表项大于等于1916992个的哈希表（对于1916992项如果用一个bit表示一个表项，实际需要234K Byte内存），同时选取7个不同的散列函数，构成一个布隆过滤器，对于每次查找，需要同时经过7个散列函数的计算，这样可以做到误算率不超过1/100。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2186c977",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
